package bjtuoj;

import java.util.Scanner;

/**
 * ClassName: Homework_3_B
 * Description:
 * date: 2021-11-09 9:31
 *
 * @author liyifan
 */
public class Homework_3_B {
    public static void main(String[] args) {
        final int MAX = 1010;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int T = scanner.nextInt();
            int M = scanner.nextInt();
            int[] cost = new int[MAX];
            int[] value = new int[MAX];
            int[] dp = new int[MAX];
            for (int i = 1; i <= M;i++) {
                cost[i] = scanner.nextInt();
                value[i] = scanner.nextInt();
            }
            for (int i = 1;i <= M;i++) {
                for (int j = T;j >= cost[i];j--) {
                    if (dp[j] < dp[j - cost[i]] + value[i]) {
                        dp[j] = dp[j - cost[i]] + value[i];
                    }
                }
            }
            System.out.print(dp[T]);
        }
    }
}
